<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
</head>

<body>
    <script>
        function test(func, n) {
            var t0 = performance.now();
            var result = func(n);
            var t1 = performance.now();
            console.log('time', (t1 - t0).toFixed(4), '毫秒:', result);
        }

        // 迭代
        // function fibonacciIterative(n) {
        //     if (n < 1) return 0;
        //     if (n <= 2) return 1;
        //     let fibNMinus2 = 0;
        //     let fibNMinus1 = 1;
        //     let fibN = n;
        //     for (let i = 2; i <= n; i++) { // n >= 2
        //         fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2)
        //         fibNMinus2 = fibNMinus1;
        //         fibNMinus1 = fibN;
        //     }
        //     return fibN;
        // }
        // function fibonacci(n){
        //     if(n === 1 || n === 0 ) return n;
        //     console.log(`fibonacci(${n-1}) + fibonacci(${n-2})`);
        //     return fibonacci(n-1) + fibonacci(n-2);
        // }
        
        // 普通递归
        // function fibonacci(n){
        //     if (n < 1) return 0; // {1}
        //     if (n <= 2) return 1; // {2}
        //     return fibonacci(n - 1) + fibonacci(n - 2); // {3}
        // }
        // 尾调用优化
        // 'use strict'
        // function fibonacci(n, current = 0, next = 1) {
        //     if(n === 1) return next;
        //     if(n === 0) return 0;
        //     console.log(`fibonacci(${n-1}) + fibonacci(${n-2})`);
        //     return fibonacci(n - 1, next, current + next);
        // }

        function fibonacciMemoization(n) {
            const memory = [0, 1]; // {1}
            const fibonacci = (n) => {
                if (memory[n] != null) return memory[n]; // {2}
                return memory[n] = fibonacci(n - 1, memory) + fibonacci(n - 2, memory); // {3}
            };
            return fibonacci(n);
        }

        test(fibonacci, 10);


    </script>
</body>

</html>